/**
 * 
 */
package np.com.baralsujan.algorithms;

import java.util.Random;

/**
 * @author sujan
 *
 */
public class QuickSortInt {

	static int count = 0;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int data[] = {8,5,1,9,4,10,6,2,3,7,45,12,56};
		print(sort(data));
	}

	public static int [] sort(int [] array) {
		return quickSort(array);
	}

	private static int [] quickSort(int [] data) {
		if(data.length <= 1) {
			return data;
		}
		int pivot = new Random().nextInt(data.length - 1);
		int [] lessList = new int[pivot - 1]; 
		int [] moreList = new int[data.length - pivot]; 
		fillBuckets(data, pivot, lessList, moreList);
		return concat(quickSort(lessList), pivot, data[pivot], quickSort(moreList));
	}
	
	public static void fillBuckets(int [] data, int pivot, int [] lessList, int [] moreList) {
		int j = 0;
		int i = 0;
		for (int k = 0; k < data.length; k++) {
			if(k == pivot) {
				continue;
			}
			if(data[k] >= data[pivot]) {
				moreList[j++] = data[k];
			} else {
				lessList[i++] = data[k];
			}
		}
	}

	public static int [] concat(int [] list, int pivot, int pivotData, int [] moreList) {
		int [] returnList = new int [list.length + pivotData + moreList.length];
		System.arraycopy(list, 0, returnList, 0, list.length);
		returnList[pivot] = pivotData;
		System.arraycopy(moreList, 0, returnList, pivot + 1, moreList.length);
		print(returnList);
		System.out.println();
		System.out.println();
		return returnList;
	}
	
	public static void print(int [] list) {
		count++;
		for (Integer integer : list) {
			System.out.print(integer + ", ");
		}
	}



}
